Subject:  Re: [ubb-acm] Probleme de geometrie computationala (schite de rezolvare 1)

 
ADVERTISEMENT
 
 
> 1. ** Se dau coordonatele a n puncte din plan
> (n<=1000). Gasiti o
> dreapta care contine cele mai multe puncte coliniare
> din punctele
> date (cormen).

algoritm O(n^2 log n):
Se cauta pt fiecare punct care este dreapta ce trece
prin acest punct si contine cele mai multe puncte din
multime pe ea. Se ordoneaza punctele in jurul fiecarui
punct in functie de unghiul pe care il fac cu
orizontala. Si acuma se parcurg punctele in ordine si
se verifica daca mai multe puncte formeaza acelasi
unghi. Sortarea e n log n si cum sunt n puncte =>
complexitatea e O(n^2 log n).

algoritm O(n^2):
Se foloseste transformarea duala. O sa explic
altadata ec e cu transformarea asta, oricum ideea e
foarte faina dar trebuie memorie O(n^2).

> 2. ** Se dau coordonatele a n puncte din plan
> (n<=1000). Se cere sa
> se gaseasca daca exista sau nu un triunghi cu
> varfurile in cele n
> puncte care sa fie dreptunghic.

algoritm O(n^2 log n):
tot asa se face ca si la problema anterioara. Se
porneste cu un indice i1 si cu un indice i2. i2 se
incrementeaza cat timp unghiul dintre p[i1], p[curent]
si p[i2] e mai mic decat 90 de grade. Dupaia i1 se
incrementeaza o data si tot asa facem o parcurgere a
punctelor sortate in O(n). Deci complexitatea e
O(n)*(O(n log n)+O(n)) = O(n^2 log n).

> 3. Se dau n puncte de coordonate intregi (n<=1000)
> se cere sa se
> determine un poligon cu varfurile in aceste puncte
> (ceva de genu
> asta s-a dat la lot prin 94).

Algoritm O(n log n):
Se sorteaza n-1 puncte in jurul primului punct si se
leaga intre ele punctele in poligon in ordinea data de
sortare.

> 4. Se dau n puncte (n<=10000). Sa se determine
> infasuratoarea
> convexa a celor n puncte (cormen,stroe).

....

> 5. ** Se dau 2 poligoane convexe fiecare avand
> maxim 1000 de
> varfuri. Se cere sa se determine intersectia lor
> (bursele agora,i-am
> dat 2 stele desi la concurs am complicat-o rau de
> tot).

Se poate verifica ce puncte din primul poligon sunt
interioare celui de al doilea si dupaia ce puncte din
al 2-lea poligon fac parte din primul si sa se adauge
la multimea asta de puncte punctele de intersectie ale
laturilor celor 2-a poligoane. Acuma mai ramane de
facut algoritmul de infasuratoare convexa pt punctele
astea. Complexitate O(n^2). Exista un algoritm destept
in O(n), da nu cred ca se merita sa fie invatat pt
concurs.

> 6. *** Se dau n puncte (n<=10000). Sa se determine
> perechea de
> puncte din cele n cu distanta maxima intre ele
> (parca am vazut-o pe
> la ceva acm, s-ar putea sa fie si in cormen, medie +
> * daca nu stiti
> cum sa o faceti, implemenatrea e *).

Evident perechea de puncte la distanta maxima se
afla pe marginile infasuratorii convexe. Daca punctele
nu sunt bine alese (adica random) o sa fie putine
puncte pe conturul infasuratoarei convexe deci aici ar
merge bruteforce O(h^2) unde h e numarul de puncte de
pe infasuratoarea convexa.
Exista 2 algoritmi mai buni O(h log h) si O(h).
Primul : pt fiecare punct se cauta cu cautare binara
al 2-lea punct.
Al doilea: se foloseste o tehnica asemanatoare cu
aceea care s-a folosit la problema cu triunghiul
dreptunghic. Avem 2 indici i1,i2 de puncte de pe
infasuratoarea convexa. cat timp distanta dintre i1 si
i2 e mai mica decat aceea dintre i1 si i2+1 se
incrementeaza i2. Se actualizeaza la fiecare pas
distanta maxima. Se incrementeaza i1. Asta se face
pana cand i1 ajunge sa fie a 2-a oara primul punct.
Evident acest algoritm are complexitatea O(h).

> 6 b *** Se dau n puncte (n<=10000). Sa se determine
> perechea de
> puncte din cele n cu distanta minima intre ele.
> (cormen si bursele
> agora)

....

> 7. * Se dau n puncte (n<=400) oricare 3
> necoliniare. Gasiti un romb
> cu varfurile in punctele date, (daca exista) (s-a
> propus pe lista de
> discutii [olimpiada] acum vreo 2 ani).

O(n^3 log n), O(n^3): Se iau oricare 3 puncte si
acest triunghi daca e isoscel se poate completa
intr-un singur fel ca sa devina romb, daca e
echilateral se poate compleat in 3 moduri si punctele
lipsa se cauta prin cautare binara intre punctele
sortate O(log n), sau se cauta intr-o tabela de
dispersie (hash table) in O(1).

O(n^2 log n), O(n^2): Amintesc proprietatea ca la
romb diagonalele sunt perpendiculare si se
injumatatesc. Se iau toate perechile de puncte, se
determina mijloacele segmentelor si panta lor si se
sorteaza sau se bvaga intr-o tabela de dispersie.
Dupaia pt fiecare mijloc si panta se cauta daca exista
in structura de date (sir ordonat sau hashtable)
acelasi punct cu panta perpendiculara. Daca orice
cautare are succes inseamna ca am gasit un romb.

> 8. Se dau n puncte (n<=500). Gasiti un patrat arie
> minima care
> contine in interior sau pe frontiera cel putin
> jumatate din punctele
> date (internet problem solving contest 2002, astia
> au probleme faine
> de tot).

Aici am uitat ca axele patratului trebuiau sa fie
paralele cu axele de coordonate.

O(n^2 log n) timp, O(n^2) memorie: Se obtine lista
ordonata a x-lor si lista ordonata a y-lor. Acuma se
foloseste o matrice unde a[i][j] inseamna ca exista un
punct in multime de coordonate x[i],y[j]. Pentru o
lungime data se poate verifica in O(n^2) daca exista
patrat cu dimensiunea asta care sa contina jumatate
din puncte. Si cu o cautare binara e gata problema.
Numarul de dimensiuni diferite e de ordinul lui n^2
(adica diferentele dintre xi,xj si yi,yj) care se pot
ordona si folosi in cautarea binara a lungimiioptime
de latura.

Pe siteul de la ipsc este o rezolvare in O(n^2 log^2
n). Cred ca si rezolvarea de mai sus poate fi
imbunatatita ca sa nu se foloseasca chestia cu
distantele de la sfarsit.

> 9. ***** Se dau n puncte in plan (n<=1000) de
> coordonate intregi
> mai mici
> in modul ca 250, oricare 3 necoliniare. Gasiti un
> triunghi cu
> varfurile in punctele date de perimetru minim. (Nu
> stiu o rezolvare
> simpla la problema cu restrictie 250, dar cred ca
> pot face o
> rezolvare un pic mai complicata pentru coordonate
> reale.) (lista
> [olimpiada])

La vremea respectiva cand s-a discutat problema se
vorbea despre o cautare locala a cate trei puncte.
Tehnicii ii zice bucketing si este foarte folositoare
uneori. Rezolvarea care o aveam eu in minte e o
generalizare a problemei distantei minime. Oricum nu
am o rezolvare eleganta la ora actuala.

> 10. ***** Se dau n puncte in plan (n<=1000) de
> coordonate reale. Se
> cere sa se determine triunghiul de arie minima cu
> varfurile in
> punctele date. (lista [olimpiada], este o rezolvare
> in N^2 dar
> destul de dura)

Csabi a facut problema asta pt proiectul de la
geometrie. E o rezolvare destul de grea care se
bazeaza pe transformare duala, arbori echilibrati de
cautare si un sweep line.

> 11. **** Se dau n drepte (n<=1000). Sa se determine
> dreptele
> vizibile din origine. (am auzit-o de la Dumitran si
> este si pe lista
> lui Francu, exista o rezlvare mai usoara cu un pic
> de cunostinte,
> daca se face muncitoreste problema e grea, daca se
> face cu idee
> problema e *)

Tot cu transformare duala.

> 12. **** Se dau n puncte in plan (n<=100000). Se
> cere sa se
> determine cercul de raza minima care le contine in
> interior pe toate
> punctele. (Balkan OI 2002, si
> http://www.fudv.ro/campion/, daca
> testele sunt slabe ... atunci problema ar merita *
> altfel exista un
> algoritm randomizat al lui Welzl care rezolva
> problema in O(N))

Cestia cu testele slabe e cea cu nr mic de puncte pe
infasuratoarea convexa.

> 13. *** Se dau n puncte in plan (n<=1000) si un
> numer real pozitiv
> r. Se cere sa se determine cercul de raza r ce
> contine numarul maxim
> de puncte in interior. (topcoder o varianta cu n mai
> mic, si CEOI 96
> sau 97, problema faina, de idee)

O(n^3). Pt orice pereche de 2 exista 2 cercuri de
raza r care au aceste puncte pe contur. In O(n) se
verifica nr de puncte in interior.

O(n^2 log n). Se considera un punct ce sa fie pe
contur. Se ordoneaza punctele in functie de ce unghi
va face centru cercului cand intra in cerc si cu ce
unghi face centrul cercului cu punctul cand ies din
cerc. La fiecare punct se incrementeaza sau
decrementeaza nr de puncte din centrul curent.

> 14. *** Se dau n dreptunghiuri cu laturile paralele
> cu axele de
> coordonate ce se pot suprapune(n<=1000) . Se cere
> aria figurii
> acoperite de aceste dreptunghiuri. (IOI 98, selectie
> lot acm
> Universitatea Bucuresti)

Se poate face o matrice cu dimensiuni 2n*2n. un fel
de matrice redusa in care a[i][j] inseamna daca
dreptunghiul (x[i],x[i+1])*(y[j],y[j+1]) este ocupat
sau nu (unde x e sirul tuturor coordonatelor x
sortate, y la fel).
Sau se poate face analiza fiecare banda de y[i]y[i+1]
si determina in O(n) aria ocupata dee pe banda asta,
daca se sorteaza dreptunghiurile in ordinea x-lor.
Se poate face si in O(n log n) cu arbori de intervale
(cormen).

> 15. *** Se dau n triunghiuri dreptunghice isoscele
> cu laturile
> perpendiculare paralele cu axele de coordonate
> (n<=1000). Se cere
> aria reuniunii triunghiurilor. (BOI 2002)

Se ordoneaza punctele pe x si se face o scanare, din
aproape in aproape se trateaza fiecare banda pe y. De
la x[i] la x[i+1].

> 16. Se da un numar natural n. Care este numarul de
> regiuni in care
> se imparte planul de n cercuri care nu se
> intersecteaza cate 3 intr-
> un punct si oricare 2 se intersecteaza in 2 puncte (
> :) problema de
> pe UVA).

Prin inductie se determina numarul de regiuni. Daca
pt n avem X(n) regiuni, cand se adauga al n+1 lea cerc
acesta se intersecteaza cu cele n cercuri in 2n
puncte. Deci o sa fie n regiuni impartite in 2 de
cercu asta, deci se adauga n regiuni noi. Recurenta e
X(n+1)= X(n)+n sau ceva de genu asta.

> 17. *** Care este numarul maxim de regiuni in care
> se inparte
> planul daca folosim n drepte. Aceeiasi problema
> pentru cercuri.
> Aceeiasi problema pentru spatiu si sfere (problema
> data la bursele
> agora) (Probleme neelementare tratate elementar
> Iaglom,Iaglom).

Se foloseste ideea de mai sus.

> 18. * Avem n drepte in plan fiecare dreapta fiind
> data prin 2
> perechi de coordonate (n<=100). Sa se determine in
> cate zone se
> imparte astfel planul (internet problem solving
> contest 2001).

Aceeiasi idee de mai sus. Se vede la fiecare pas
cate drepte intersecteaza o dreapta si asa se vede
cate regiuni noi se adauga la cele vechi.

> 19. ** (problema de-a mea :)) Se dau n de puncte de
> coordonate
> intregi (n<=10000). Sa se determine cate triunghiuri
> cu varfurile in
> punctele astea au ca arie un numar intreg.

Dupa cum stiti aria unui triunghi e abs(1/2*
det(x1,y1,1,x2,y2,1,x3,y3,1)) deci daca aria unui
triunghi e intreaga daca determinantul e par.
Paritatea determinantului e data de paritatile
coordonatelor. Acuma clasificam coordonatele in 4
clase: (x par, y par),(x impar, y par)(x impar, y
impar)(x par, y impar). Si ce mai ramane de facut e sa
verificam ce triplete de clase dau determinant par.

> 20. * Sa se determine aria unui poligon oarecare ce
> are n varfuri
> (n<=10000).(judeteana Bistrita,97)

http://www.faqs.org/faqs/graphics/algorithms-faq/
Aici sunt cateva chestii simple de geometrie
computationala printre care si aria unui poligon.

> 21. Sa se determine daca un poligon cu n varfuri
> (n<=100000) este
> convex.

Daca fiecare triunghi de 3 puncte consecutive de pe
marginea poligonului are acelasi semn atunci poligonul
e convex.


> 22. Sa se determine daca un poligon are varfurile
> date in sens
> trigonometric sau sens orar (n<=100000).

Daca aria are un semn punctele sunt date in sens
orar, daca nu ele sunt date in sens trigonometric. Se
verifica experimental ce sens e bun.

Altfel: se determina cel mai de jos punct de pe
poligon si se verifica in ce sens e orientat
triunghiul cu trei puncte consecutive de pe conturul
poligonului pt care punctul cel mai de jos e la
mijloc.

>23. Sa se determine centrul de greutate al unui
>poligon oarecare ce
>are n varfuri (n<=10000). (acm central european
>region, olimpiada
>online)
http://www.faqs.org/faqs/graphics/algorithms-faq/
Tot acolo, se bazeaza pe formula ariei.

>24. Se dau n segmente (n<=100). Sa se determine o
>dreapta ce
>intersecteaza numarul maxim posibil de segmente.
>(lista [olimpiada])

Orice dreapta ce intersecteaza numarul maxim de
segmente poate fi translatata astfel incat sa
intersecteze acelasi numar de segmente dar sa aiba pe
ea o extremitate de segment, dupaia poate fi rotita sa
aiba inca o extremitate pe ea. Deci complexitate
O(n^3).

Se poate si in O(n^2 log n) cu ideea de sortare in
jurul punctului.

>25. Se dau doua multimi de n si m puncte (n,m<=300).
>Sa se determine o dreapta care separa aceste doua
>multimi. (baraj 98)

O dreapta de separare se poate translata pana cand
intalneste un varf al unui poligon. Acuma pt fiecare
punct se testeaza daca punctele din celalalt poligon
sunt in acelasi semiplan. Asta se face determinand
unghiul cu fiecare pct din celalalt poligon si se vede
daca diferenta intre cel mai mic si cel mai mare punct
ca unghi e <=180. (mai e de verificat si daca aceasta
dreapta determinata nu intersecteaza primul poligon)

>26. * Se da un poligon oarecare cu n varfuri
>(n<=1000). Se dau m puncte (m<=1000). Sa se determine

>care dintre puncte sunt interioare
>poligonului. (pregatire lot 99)

http://www.faqs.org/faqs/graphics/algorithms-faq/

>27. *** Se da un poligon convex cu n varfuri
>(n<=1000). Se dau m
>puncte (m<=100000). Sa se determine care dintre
>puncte sunt interioare poligonului. (balcaniada 99,
>cu date ca si la problema anterioara)

Se considera un vf al poligonului si fasciculele
determinate de punctu asta si cate 2 semidrepte ce
pleaca din el inspre cate 2 puncte consecutive de pe
poligon. Cu cautare binara se gaseste fascicolul in
care e fiecare punct si acuma mai ramane de verificat
daca punctul respectiv e interior triunghiului.


>28. *** Se da un poligon convex de n noduri
>(n<=10000) si m drepte
>(m<=10000). Sa se determine cate drepte intersecteaza
>poligonul. (baraj 98, ceoi 2002)

tot cautare binara

>29. * Se dau n puncte de coordonate intregi in plan,
>sa se determine numarul de puncte de coordonate
>intregi de pe contrulul poligonului, aria
>poligonului, si numarul de puncte de coordonate
>intregi interioare poligonului. (selectie acm Babes
>2003 :))

Parca ii zice formula lui pick la chestia ce am
folosit-o in concurs se gaseste in Probleme
neelementare tratate elementar (Iaglom, Iaglom).

Pt determinarea numarului de puncte de coordonate
intregio pe un segment cu capetele de coordonate
intregi se foloseste algoritmul lui Euclid.

>30. *** Se da un poligon convex cu n varfuri
>(n<=10000) de coordonate reale intre 0 si 30000. Sa
>se determine numarul de puncte de coordonate intregi
>din interiorul poligonului. (eu am vazut-o pe
>lista lui Francu, dar cred ca e si pe acm.timus.ru)

O(n)

>31. *** Se dau n puncte (n<=1000) intr-un dreptunghi.
>Sa se determine dreptunghiul de arie maxima continut
>in dreptunghiul initial cu laturile paralele cu cele
>ale dreptunghiului initial, care nu contine nici un
>punct in interior. (El Judge, UVA, CEOI 96
>sau 97)
O(n^2) poate va explica csibi sau adi.

O sa mai lucrez la mailu asta sa le redactez mai
bine. Daca aveti idei noi sau corecturi var rog
trimiteti-mi.

Salut,
Cosmin
 
